In many storage systems, it is desirable to use clustering to provide improved performance. Over time, a clustered storage system may need to add or remove storage controllers and associated storage devices, either to replace failed or failing storage devices and storage controllers, or to increase capacity as the amount of data stored in the cluster increases. It is further desirable to provide for online cluster expansion, where such addition and removal of storage devices and storage controllers of the clustered storage system is performed while continuing to service input-output requests directed to data stored in the clustered storage system. Conventional approaches for such cluster expansion, however, can be problematic in terms of performance during the deletion or other release of physical capacity of the storage devices in the clustered storage system.